package com.codecrane.core.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

/**
 * 基于二分搜索实现的权重随机工具类
 * Created by crane on 16/7/8.
 */
public class BinaryWeightRandom<T> extends WeightRandom<T> {
    int[] array;
    Object[] results;
    int total;

    public BinaryWeightRandom(Map<T, Integer> data) {
        super(data);
    }

    @Override
    public void init() {
        List<Integer> arrayList = new ArrayList<Integer>();
        List<T> resultList = new ArrayList<T>();
        int total = 0;
        for (Map.Entry<T, Integer> each : data.entrySet()) {
            final T k = each.getKey();
            final Integer v = each.getValue();
            if (null == v || v == 0) {
                continue;
            }
            total += v;
            arrayList.add(total);
            resultList.add(k);
        }
        this.total = total;
        array = new int[arrayList.size()];
        results = new Object[arrayList.size()];

        for (int i = 0; i < arrayList.size(); i++) {
            array[i] = arrayList.get(i);
            results[i] = resultList.get(i);
        }
    }

    @Override
    public T random() {
        int r = this.ran.nextInt(total) + 1;
        return random(r);
    }

    @Override
    public T random(int ran) {
        if (ran < 0) {
            ran = -ran;
        }
        ran = ran % total;
        ran++;
        int idx = Arrays.binarySearch(array, ran);
        if (idx < 0) {
            idx = -1 - idx;
        }
        return (T) results[idx];
    }
}
